// 67. Add Binary
// Given two binary strings, return their sum (also a binary string).

// For example,
// a = "11"
// b = "1"
// Return "100".

package main

import "fmt"

func addBinary(a string, b string) string {
	aLen, bLen := len(a), len(b)
	if aLen == 0 && bLen == 0 {
		return ""
	}

	i, j, carry, num, count := aLen-1, bLen-1, byte(0), byte(0), aLen
	if count < bLen {
		count = bLen
	}
	result := make([]byte, count+1)

	for ; i >= 0 && j >= 0; i, j = i-1, j-1 {
		num = (a[i] - '0') + (b[j] - '0') + carry
		if num > 1 {
			carry = 1
			num -= 2
		} else {
			carry = 0
		}

		result[count] = num + '0'
		count--
	}

	if i == j {
		if carry > 0 {
			result[count] = '1'
			count--
		}
		return string(result[count+1:])
	}

	if j >= 0 {
		a, i = b, j
	}

	for ; i >= 0; i-- {
		num = (a[i] - '0') + carry
		if num > 1 {
			carry = 1
			num -= 2
		} else {
			carry = 0
		}

		result[count] = num + '0'
		count--
	}

	if carry > 0 {
		result[count] = '1'
		count--
	}

	return string(result[count+1:])
}

func main() {
	a, b := "10101", "110000"
	// 1000101
	//  100101
	fmt.Printf("%v\n", addBinary(a, b))
}
